Background: Borderline ovarian tumors (BOTs) are a subset of epithelial ovarian tumors with low malignant potential but significant risk of relapse (10% to 30%). Unfortunately, surgical prognostic factors for BOT relapse have not been clearly identified, probably due to the use of heterogeneous surgical definitions and limited follow-up. The aim of this study was to assess potential relapse risk factors using standard surgical definitions and long follow-up. Methods: All patients diagnosed with BOT for a period of more than 10 years in a single institution were included in the analysis. Complete surgical staging was defined as the set of procedures that follow standard guidelines for staging surgery (except lymphadenectomy), performed either with one or two interventions. Fertility-sparing surgeries that preserved one ovary and the uterus but included all the remaining procedures were classified as complete staging. The relationship between potential risk factors and time to BOT relapse was assessed by log-rank tests corrected for multiple comparisons and Cox regression. Results: Forty-six patients with a median follow-up of 5.4 years were included, of whom 91.3% had been diagnosed as FIGO stage I disease and 45.7% had received complete staging surgery. Five relapses were detected (10.9%), all of them in women who had been diagnosed with stage I disease and had received incomplete staging surgery. Log-rank tests confirmed the association between incomplete staging surgery and shorter time to BOT relapse. Conclusions: Complete staging surgery should be considered a cornerstone of BOT treatment in order to minimize the risk of relapse.